package arrayandstring;

import java.util.Stack;
/**
 * https://leetcode-cn.com/problems/simplify-path/
 */
public class M71_SimplifyPath {
    /**
     * 时间复杂度 O(n) 空间复杂度 O(n)
     */
    public static String simplifypath(String path) {
        // 分割字符串
        String[] str = path.split("/"); // ["","a","b","","c","..","d"]
        Stack<String> stack = new Stack<>();
        // 遍历数组
        for (int i = 0; i < str.length; i++) {
            // [".."] 处理
            if ("..".equals(str[i])) {
                // 栈非空弹出栈顶元素否则就不做处理
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } 
            // [".",""] 表示当前目录本身就不做处理了
            else if (!("".equals(str[i]) || ".".equals(str[i]))) {
                // 将文件名 or 目录名压栈
                stack.push(str[i]);
            }
        }
        // 栈为空就返回根目录
        if (stack.isEmpty()) return "/";
        // 遍历栈
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop());
            sb.insert(0, "/");
        }
        return sb.toString();
    }
    public static void main(String[] args) {
        simplifypath("/a/b//c/../d/");
        simplifypath("/home//foo/");
        simplifypath("/../..//cc");
    }
}

